nLab nondeterministic automaton

Definitions

(For the moment, mostly as an example of a coalgebra for an endofunctor and to start discussion of models for non-determinism.)

This will give the classical definition as a non-deterministic state-based system and then show how to turn that form into the coalgebraic form.

Definition

A non-deterministic automaton consists of the following data:

• a set of states, $Q$;

• a set, $\Sigma$, of input symbols ;

• a function, $\delta : Q\times \Sigma \to \mathcal{P}(Q)$, called the next state relation,

and

• a predicate, $final : Q \to bool = \{\bot, \top\}$, the boolean domain.

In the usual interpretation if the automaton is in state $q$, and is ‘given’ the input $\sigma$, then it changes to being in one of the states in the subset, $\delta(q,\sigma)$, of $Q$.

The ‘final’ predicate, of course, returns $\top$ if a state is a final state and $\bot$ otherwise. (There will, in general, be a set of final or ‘accept’ states.)

(For the moment we will not look at the links between automata and languages.)

Properties

Coalgebraic description

The first step in transforming the above definition to the coalgebraic form is to curry $\delta$, so as to obtain it in the form $\delta : Q\to \mathcal{P}(Q)^\Sigma$. We thus have for a state, $q\in Q$, $\delta(q,) : \Sigma \to \mathcal{P}(Q)$. We then also have a product function

$$\alpha = \delta \times (final) : Q \to \mathcal{P}(Q)^\Sigma\times bool.$$

If we now write $HQ = \mathcal{P}(Q)^\Sigma\times bool$, we get a functor (for you to check) $H : Set \to Set$ and the non-deterministic automaton corresponded precisely to a coalgebra, $(Q,\alpha)$, for $H$.

Related concepts

• automaton

• non-deterministic computation

References

Monographs:

• M. V. Lawson, Finite Automata, Google books

See also:

• Wikipedia, Automata theory

Discussion via coalgebra:

• Alexander Kurz: Coalgebras and Modal Logic. Course Notes for ESSLLI 2001, Version of October 2001. Appeared on the CD-Rom ESSLLI’01, Department of Philosophy, University of Helsinki, Finland, available from site.

Discussion of non-deterministic automata as 1-dimensional defect TQFTs:

• Paul Gustafson, Mee Seong Im, Remy Kaldawy, Mikhail Khovanov, Zachary Lihn, Automata and one-dimensional TQFTs with defects [arXiv:2301.00700]

Review:

• Mee Seong Im, Correspondence between automata and one-dimensional Boolean topological theories and TQFTs, talk at QFT and Cobordism, CQTS (Mar 2023) [web, video:YT]